<?php
/**
 * Created by PhpStorm.
 * User: lili
 * Date: 2019/3/23
 * Time: 10:41
 */

require_once "../tools/tools.php";


if('cli'!==PHP_SAPI){
    echo "必须使用cli";
    exit();
}


echo "一群猴子排成一圈，按1，2，...，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，
从它后面再开始数，再数到第m只，在把它踢出去...，如此不停的进行下去，直到最后只剩下
一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n,输出最后那个大王的编号。\n";


fwrite(STDOUT,"输入n:");
$n = trim(fgets(STDIN));


fwrite(STDOUT,"输入m:");
$m = trim(fgets(STDIN));



echo "你输入的n:$n,m:$m\n";

/**
 *
 * 不断循环数组，遇到第m个，就把其变0；
 * 遇到0跳过，忽略他
 * 不依赖语言，第一种方法使用了队列的形式，难移植
 *
 *
 * */
function monkey($n ,$m){
    $arr = range(1,$n);
    $i = 0;//定位，($i mod n) 是下标
    $t = 0;//踢出去的数量
    $mod = 0;//计数，哪个是m位
    $c=0;//统计数数的次数
    while ($n-$t>1){
        if($arr[$i%$n]==0){
            //假如这个位置本身就是0，也就是已经踢出去了，跳过
            $i++;
            continue;
        }
        $mod=$mod+1;
        $mod=$mod%$m;
        if ($mod==0){//第m个猴子
            //则要把该猴子踢出去
            $arr[$i%$n]=0;
            $t++;
        }
        $c++;
        $i++;
    }
    for($j=0;$j<count($arr);$j++){
        if($arr[$j]!==0){ //遍历数组，找出唯一一个不为0的值，那个就是最后的大王
            $h=$arr[$j];
        }
    }
    return [
        'c'=>$c,//数数的次数
        'h'=>$h//大王编号
    ];;
}

$time_start = microtime_float();

$res = monkey($n,$m);

//var_dump($res);

echo "最后的大王为：{$res['h']}号\n";
echo "数数次数：{$res['c']}\n";
$time_end = microtime_float();
$time = $time_end - $time_start;

echo "Did nothing in $time seconds\n";